//#include "stc.h"
#include<iostream>

#define NULL 0

struct NameIndex
{
        char*        name;
        int          data;
        struct NameIndex * parent;
        struct NameIndex * left;
        struct NameIndex * right;
};

void copyStr(char *str1, char *str2)
{
	while(*str2 != 0)
	{
		*str1 = *str2;
		str1++;
		str2++;
	}
	*str1 = '\0';
}

int cmpStr(const char* src,const char* des);
int Insert(struct NameIndex* head, char* name);
int Delete(struct NameIndex* head);
int MoveSmallest(struct NameIndex* head);
int MoveSmaller(struct NameIndex* head);
int MoveLarger(struct NameIndex* head);
int MoveLargest(struct NameIndex* head);
int searchName(struct NameIndex* head, struct NameIndex *top, char *fullname);
int Search(struct NameIndex* head, char* fullname);
int PartialSearch(struct NameIndex* root, char* partialname);
 
int SetData(struct NameIndex* head, int data);
int GetData(struct NameIndex* head, int* data);
void DeleteNodeName(NameIndex *&tree);
 
void moveTop(struct NameIndex* head)
{
	NameIndex *cursor = head->right;
	while(cursor->parent != NULL)
	{
		cursor = cursor->parent;
	}
	head->right = cursor;
}

int InsertName(struct NameIndex* head, struct NameIndex* top, char* name)
{
	if(top == NULL)
	{
		top = new NameIndex;
		top->name = new char[17];
		copyStr(top->name, name);
		top->parent = NULL;
		top->left = NULL;
		top->right = NULL;
		head->left = top;
		head->right = top;
		return 1;
	}
	else
	{
		if(cmpStr(top->name, name) > 0)
		{
			if(top->left != NULL)
				InsertName(head, top->left, name);
			else
			{
				top->left = new NameIndex;
				top->left->name = new char[17];
				copyStr(top->left->name, name);
				top->left->parent = top;
				top->left->left = NULL;
				top->left->right = NULL;
				head->right = top->left;
				return 1;
			}
		}
		else if(cmpStr(top->name, name) < 0)
		{
			if(top->right != NULL)
				InsertName(head, top->right, name);
			else
			{
				top->right = new NameIndex;
				top->right->name = new char[17];
				copyStr(top->right->name, name);
				top->right->parent = top;
				top->right->left = NULL;
				top->right->right = NULL;
				head->right = top->right;
				return 1;
			}
		}
	}
	return 1;
}

int Insert(struct NameIndex* head, char* name)
{
	NameIndex *top = head->left;
	InsertName(head, top, name);
	return 1;
}

NameIndex* getSuccessor(NameIndex *node)
{
    while(node->right != NULL)
    node = node->right;
    return node;
}

NameIndex* removeNode(NameIndex *node, char* name)
{
    if(node == NULL)
		return node;

	if(cmpStr(name, node->name) == 0)
    {
		NameIndex *retval = new NameIndex;
    
		if(node->left == NULL)
		{
			retval = node->right;
			delete node;
			return retval;
		}
		else if(node->right == NULL)
		{
			retval = node->left;
			delete node;
			return retval;
		}
		else
		{
			NameIndex *s = new NameIndex;
			s = getSuccessor(node->left);
			copyStr(node->name, s->name);
			node->data = s->data;
			node->left = removeNode(node->left, s->name);
		}
    }
    else if(cmpStr(name, node->name) < 0)
		node->left = removeNode(node->left, name);
    else
		node->right = removeNode(node->right, name);

    return node;
}

int Delete(struct NameIndex* head)
{
	NameIndex *cursor = head->right;
	removeNode(cursor, cursor->name);
	return 1;
}
 
int MoveSmallest(struct NameIndex* head)
{
	NameIndex *top = head->left;
	while(top->left != NULL)
	{
		top = top->left;
	}
	printf("\n Move to smallest : %s", top->name);
	head->right = top;
	return 1;
}

int MoveSmaller(struct NameIndex* head)
{
	int data;
	GetData(head, &data);
	data--;
	char *s = new char[2];
	s[0] = data + 'A';
	s[1] = 0;
	searchName(head, head->left, s);
	return 1;
}

int MoveLarger(struct NameIndex* head)
{
	int data;
	GetData(head, &data);
	data++;
	char *s = new char[2];
	s[0] = data + 'A';
	s[1] = 0;
	searchName(head, head->left, s);
	return 1;
}

int MoveLargest(struct NameIndex* head)
{
	NameIndex *top = head->left;
	while(top->right != NULL)
	{
		top = top->right;
	}
	head->right = top;
	return 1;
}

int searchName(struct NameIndex* head, struct NameIndex *top, char *fullname)
{
	if(top == NULL)
		return 0;
	else
	{
		if(cmpStr(top->name, fullname) > 0)
		{
			if(top->left == NULL)
				return 0;
			else
				searchName(head, top->left, fullname);
		}
		else if(cmpStr(top->name, fullname) < 0)
		{
			if(top->right == NULL)
				return 0;
			else
				searchName(head, top->right, fullname);
		}
		else
		{
			head->right = top;
			return 1;
		}
	}
}
 
int Search(struct NameIndex* head, char* fullname)
{
	NameIndex *top = head->left;
	return searchName(head, top, fullname);
}

int PartialSearch(struct NameIndex* root, char* partialname);
 
int SetData(struct NameIndex* head, int data)
{
	NameIndex *cursor = head->right;
	cursor->data = data;
	return 1;
}

int GetData(struct NameIndex* head, int* data)
{
	NameIndex *cursor = head->right;
	*data = cursor->data;
	return 1;
}

void deleteNode(char *name, NameIndex *&node)
{
	if(cmpStr(name, node->name) < 0)
		deleteNode(name, node->left);
	else if(cmpStr(name, node->name) > 0)
		deleteNode(name, node->right);
	else
		makeDeletion(node);
}

void makeDeletion(NameIndex *&node)
{
	NameIndex *temp;
	if(node == NULL)
		return;
	else if(node->right == NULL)
	{
		temp = node;
		node = node->left;
		delete temp;
	}
	else if(node->left == NULL)
	{
		temp = node;
		node = node->right;
		delete temp;
	}
	else
	{
		temp = node->right;
		while(temp->left)
		{
			temp = temp->left;
		}
		temp->left = node->left;
		temp = node;
		node = node->right;
		delete temp;
	}
}